package stack.programs.bad;

//ORIGINAL VERSION:
//Copyright � 2002�2010, Robert Sedgewick and Kevin Wayne. 
//Last updated: Tue Aug 14 11:15:04 EDT 2012.
//From: http://algs4.cs.princeton.edu/13stacks/Stack.java.html

import java.util.Iterator;
import java.util.NoSuchElementException;

import stack.programs.Stack;

//Properties a Stack implementation needs to have to be correct:
//1: LIFO 
//2.1: popping the Stack with pop() returns the element last added
//2.2: popping the Stack with pop() removes the element last added
//3.1: looking at the Stack with peek() returns the element last added
//3.2: looking at the Stack with peek() does not remove the element last added
//4.1: pushing onto the Stack with push(item) changes the top element into the item
//4.2: pushing onto the Stack with push(item) moves the old last pushed item down the stack one.
//5: size() must return the amount of elements in the Stack
//6: check() must make sure all internal invariants are still there:
//6.1: an empty stack has no first element
//6.2: a stack of size one has one element
//6.3: a stack larger than size one has more than one element
//7: isEmpty() is only true if the stack size is also 0

public class StackBreakingProperty3bAnd4b<Item> implements Stack<Item> {
	private int N;          // size of the stack
 private Node first;     // top of stack

 // helper linked list class
 private class Node {
     private Item item;
     private Node next;
 }

/**
  * Create an empty stack.
  */
 public StackBreakingProperty3bAnd4b() {
     first = null;
     N = 0;
     assert check();
 }

/**
  * Is the stack empty?
  */
 public boolean isEmpty() {
     return first == null;
 }

/**
  * Return the number of items in the stack.
  */
 public int size() {
     return N;
 }

/**
  * Add the item to the stack.
  */
 public void push(Item item) {
	//Node oldfirst = first;
     first = new Node();
     first.item = item;
     //first.next = oldfirst;
     N++;
     assert check();
 }

/**
  * Delete and return the item most recently added to the stack.
  * @throws java.util.NoSuchElementException if stack is empty.
  */
 public Item pop() {
     if (isEmpty()) throw new NoSuchElementException("Stack underflow");
     Item item = first.item;        // save item to return
     first = first.next;            // delete first node
     N--;
     //assert check();
     return item;                   // return the saved item
 }


/**
  * Return the item most recently added to the stack.
  * @throws java.util.NoSuchElementException if stack is empty.
  */
 public Item peek() {
	 if (isEmpty()) throw new NoSuchElementException("Stack underflow");
     Item item = first.item;        // save item to return
     first = first.next;            // delete first node
     N--;
     //assert check();
     return item;                   // return the saved item
 }

/**
  * Return string representation.
  */
 public String toString() {
     StringBuilder s = new StringBuilder();
     for (Item item : this)
         s.append(item + " ");
     return s.toString();
 }
    

 // check internal invariants
 private boolean check() {
     if (N == 0) {
         if (first != null) return false;
     }
     else if (N == 1) {
         if (first == null)      return false;
         if (first.next != null) return false;
     }
     else {
         if (first.next == null) return false;
     }

     // check internal consistency of instance variable N
     int numberOfNodes = 0;
     for (Node x = first; x != null; x = x.next) {
         numberOfNodes++;
     }
     if (numberOfNodes != N) return false;

     return true;
 } 


/**
  * Return an iterator to the stack that iterates through the items in LIFO order.
  */
 public Iterator<Item> iterator()  { return new ListIterator();  }

 // an iterator, doesn't implement remove() since it's optional
 private class ListIterator implements Iterator<Item> {
     private Node current = first;
     public boolean hasNext()  { return current != null;                     }
     public void remove()      { throw new UnsupportedOperationException();  }

     public Item next() {
         if (!hasNext()) throw new NoSuchElementException();
         Item item = current.item;
         current = current.next; 
         return item;
     }
 }
}
